/*
2017/2/10 euler筛法求1..n的欧拉函数。
本次主要学习：euler筛法。求素数速度（线性）快于筛选法
（NloglogN）
相关资料，问度娘
特点：任何一个合数n只被筛一次，且被其包含的最小素因子p筛去，但是是在n/p时被筛去的。
能力：线性处理积性函数在[1..n]的值。
*/

/*
原理：任何合数都能表示成一系列质数的积。
    每个合数必有一个最小素因子，每个合数仅被其最小素因子刷一遍
*/

#include <iostream>
#include <cstring>

using namespace std;

int eulerPrime(int n); //欧拉筛法求素数
int euler(int n);  //欧拉筛法求欧拉函数

const int MAX = 100000 + 1;

int prime[MAX];
bool notPrime[MAX];
int phi[MAX];

int main(void) {
  int n;
  std::cin >> n;

  std::cout << euler(n) << '\n';
  return 0;
}


int eulerPrime(int n)
{
  int count = 0;
  memset(notPrime,0,sizeof(notPrime));
  for (int i = 2; i < n; i++)
  {
    if(!notPrime[i]) prime[count++] = i;
    for (int j = 0; j < count && i*prime[j] < n; j++) {
      notPrime[i*prime[j]] = true;
      if(i % prime[j] == 0)
        break;
    }
  }

  for (int i = 0; i < count; i++) {
    std::cout << i <<"  " << prime[i] << '\n';
  }

  return count;
}



/*
需要用到如下性质(p为质数)：
    1. phi(p)=p-1   因为质数p除了1以外的因数只有p，
        故1至p的整数只有p与p不互质
    2. 设P是素数，
      若p是x的约数，则E(x*p)=E(x)*p.
      若p不是x的约数，则E(x*p)=E(x)*E(p)=E(x)*(p-1)
*/
int euler(int n)
{
  n = n+10;
  int count = 0;
  memset(notPrime,0,sizeof(notPrime));

  phi[1] = 1;
  for (int i = 2; i < n; i++)
  {
    if(!notPrime[i])
    {
      phi[i] = i-1;
      prime[count++] = i;
    }
    for (int j = 0; j < count && i*prime[j] < n; j++) {
      notPrime[i*prime[j]] = true;
      //phi[i*prime[j]] = 1;
      if(i % prime[j] == 0)
      {
        phi[i*prime[j]] = phi[i] * prime[j];
        break;
      }
      else
      {
        phi[i*prime[j]] = phi[i]*(prime[j]-1);
      }
    }
  }

  // for (int i = 0; i < n; i++) {
  //   std::cout << i <<"  " << phi[i] << '\n';
  // }

  return phi[n-10];
}
